Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning
Identifieur interne : 002225 ( Main/Exploration ); précédent : 002224; suivant : 002226Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning
Auteurs : Raz Nissim [Israël] ; Joerg Hoffmann [France] ; Malte Helmert [Allemagne]Source :
Abstract
A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&S yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a simple hybrid of two such variants is competitive with the leading heuristic LM-cut.
Url:
Affiliations:
- Allemagne, France, Israël
- Grand Est, Lorraine (région)
- Nancy
- Institut national polytechnique de Lorraine, Université Nancy 2, Université de Lorraine
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 001775
- to stream Hal, to step Curation: 001775
- to stream Hal, to step Checkpoint: 001C88
- to stream Main, to step Merge: 002269
- to stream Main, to step Curation: 002225
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning</title><author><name sortKey="Nissim, Raz" sort="Nissim, Raz" uniqKey="Nissim R" first="Raz" last="Nissim">Raz Nissim</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-35626" status="VALID"><orgName>Ben Gurion University</orgName><desc><address><addrLine>Beer Sheva</addrLine><country key="IL"></country></address></desc><listRelation><relation active="#struct-300759" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300759" type="direct"><org type="institution" xml:id="struct-300759" status="VALID"><orgName>Ben-Gurion University of the Negev</orgName><desc><address><country key="IL"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Israël</country></affiliation></author><author><name sortKey="Hoffmann, Joerg" sort="Hoffmann, Joerg" uniqKey="Hoffmann J" first="Joerg" last="Hoffmann">Joerg Hoffmann</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2355" status="OLD"><idno type="RNSR">200218290B</idno><orgName>Autonomous intelligent machine</orgName><orgName type="acronym">MAIA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/maia</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Helmert, Malte" sort="Helmert, Malte" uniqKey="Helmert M" first="Malte" last="Helmert">Malte Helmert</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-106863" status="VALID"><orgName>Center for Cognitive Science [Freiburg]</orgName><desc><address><country key="DE"></country></address><ref type="url">http://portal.uni-freiburg.de/cognition/</ref></desc><listRelation><relation active="#struct-68615" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-68615" type="direct"><org type="institution" xml:id="struct-68615" status="VALID"><orgName>University of Freiburg [Freiburg]</orgName><desc><address><addrLine>Friedrichstr. 39 79098 Freiburg</addrLine><country key="DE"></country></address><ref type="url">http://www.uni-freiburg.de/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Allemagne</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00592438</idno><idno type="halId">inria-00592438</idno><idno type="halUri">https://hal.inria.fr/inria-00592438</idno><idno type="url">https://hal.inria.fr/inria-00592438</idno><date when="2011-07-16">2011-07-16</date><idno type="wicri:Area/Hal/Corpus">001775</idno><idno type="wicri:Area/Hal/Curation">001775</idno><idno type="wicri:Area/Hal/Checkpoint">001C88</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001C88</idno><idno type="wicri:Area/Main/Merge">002269</idno><idno type="wicri:Area/Main/Curation">002225</idno><idno type="wicri:Area/Main/Exploration">002225</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning</title><author><name sortKey="Nissim, Raz" sort="Nissim, Raz" uniqKey="Nissim R" first="Raz" last="Nissim">Raz Nissim</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-35626" status="VALID"><orgName>Ben Gurion University</orgName><desc><address><addrLine>Beer Sheva</addrLine><country key="IL"></country></address></desc><listRelation><relation active="#struct-300759" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300759" type="direct"><org type="institution" xml:id="struct-300759" status="VALID"><orgName>Ben-Gurion University of the Negev</orgName><desc><address><country key="IL"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Israël</country></affiliation></author><author><name sortKey="Hoffmann, Joerg" sort="Hoffmann, Joerg" uniqKey="Hoffmann J" first="Joerg" last="Hoffmann">Joerg Hoffmann</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2355" status="OLD"><idno type="RNSR">200218290B</idno><orgName>Autonomous intelligent machine</orgName><orgName type="acronym">MAIA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/maia</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Helmert, Malte" sort="Helmert, Malte" uniqKey="Helmert M" first="Malte" last="Helmert">Malte Helmert</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-106863" status="VALID"><orgName>Center for Cognitive Science [Freiburg]</orgName><desc><address><country key="DE"></country></address><ref type="url">http://portal.uni-freiburg.de/cognition/</ref></desc><listRelation><relation active="#struct-68615" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-68615" type="direct"><org type="institution" xml:id="struct-68615" status="VALID"><orgName>University of Freiburg [Freiburg]</orgName><desc><address><addrLine>Friedrichstr. 39 79098 Freiburg</addrLine><country key="DE"></country></address><ref type="url">http://www.uni-freiburg.de/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Allemagne</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&S yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a simple hybrid of two such variants is competitive with the leading heuristic LM-cut.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>France</li><li>Israël</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Nancy</li></settlement><orgName><li>Institut national polytechnique de Lorraine</li><li>Université Nancy 2</li><li>Université de Lorraine</li></orgName></list><tree><country name="Israël"><noRegion><name sortKey="Nissim, Raz" sort="Nissim, Raz" uniqKey="Nissim R" first="Raz" last="Nissim">Raz Nissim</name></noRegion></country><country name="France"><region name="Grand Est"><name sortKey="Hoffmann, Joerg" sort="Hoffmann, Joerg" uniqKey="Hoffmann J" first="Joerg" last="Hoffmann">Joerg Hoffmann</name></region></country><country name="Allemagne"><noRegion><name sortKey="Helmert, Malte" sort="Helmert, Malte" uniqKey="Helmert M" first="Malte" last="Helmert">Malte Helmert</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002225 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002225 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:inria-00592438
|texte= Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning
}}
| This area was generated with Dilib version V0.6.33. |  |